package 微软笔试;

class Solution {
    public int solution(int[] A) {
        int length = A.length;
        for (int i = 0; i < length; i++) {
            while(A[i]>0 && A[i]-1<length&&A[A[i]-1]!=A[i]){
                swap(A,i,A[i]-1);
            }
        }
        for (int i = 0; i < length; i++) {
            if(A[i]!=i+1){
                return i+1;
            }
        }
        return length+1;
    }

    public void swap(int[] A,int i,int j){
        int tmp = A[i];
        A[i] = A[j];
        A[j] = tmp;
    }
}
